package cxydmmszl.chapter04.t060;

import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 换钱的方法数
 * <li style="color: red;">Desc</li>
 * 给定数组 arr，设数组长度为 n，arr中所有的值都为正整数且不重复。
 * 每个值代表一种面值的货币，每种面值的货币可以使用任意张，
 * 再给定一个整数 aim，代表要找的钱数，求换钱的方法数有多少种。
 * 由于方法的种数比较大，所以要求输出对 10^9+7 进行取模后的答案。<br/><br/>
 * 输入描述：<br/>
 * 输出包括两行，第一行包括两个整数 n(0<=n<=1000) 和 aim(0≤aim≤20000)。
 * 第二行包含 n 个整数，表示 arr 数组 (1<=arr[i]<=1e9)。<br/><br/>
 * 输出描述：<br/>
 * 输出一个整数，表示换钱的方法数对 10^9+7 取模后的答案。
 * <li style="color: red;">Link</li> CD19
 *
 * @author habitplus
 * @since 2021-09-01 16:57
 */
public class Main {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int ans = numOfChangeCoins5(arr, aim);
        System.out.println(ans);
    }

    // 动态规划
    private static int numOfChangeCoins3(int[] coins, int aim) {
        if (coins == null || coins.length < 1 || aim < 0) {
            return 0;
        }

        int n = coins.length;

        // dp[i][j] 表示在使用 coins[0...i] 货币的情况下，组成钱数 j 有多少种方法
        int[][] dp = new int[n][aim + 1];

        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }

        // 只使用 coins[0] 能组成的钱数
        for (int i = 1; coins[0] * i <= aim; i++) {
            dp[0][coins[0] * i] = 1;
        }

        int num;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                num = 0;
                for (int k = 0; j - coins[i] * k >= 0; k++) {
                    num += dp[i - 1][j - coins[i] * k];
                }
                dp[i][j] = num % MOD;
            }
        }

        return dp[n - 1][aim];
    }

    // 动态规划：优化成时间：O(N * aim)
    private static int numOfChangeCoins4(int[] coins, int aim) {
        if (coins == null || coins.length < 1 || aim < 0) {
            return 0;
        }

        int n = coins.length;

        // dp[i][j] 表示在使用 coins[0...i] 货币的情况下，组成钱数 j 有多少种方法
        int[][] dp = new int[n][aim + 1];

        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }

        // 只使用 coins[0] 能组成的钱数
        for (int i = 1; coins[0] * i <= aim; i++) {
            dp[0][coins[0] * i] = 1;
        }


        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
//                // 相当于 不用 coins[i] 和 使用至少一张 coins[i]
//                for (int k = 0; j - coins[i] * k >= 0; k++) {
//                    num += dp[i-1][j - coins[i] * k];
//                }
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i]) {
                    dp[i][j] = (dp[i][j] + dp[i][j - coins[i]]) % MOD;
                }
            }
        }

        return dp[n - 1][aim];
    }

    // 动态规划：优化成时间：O(N * aim)，空间：O(aim)
    private static int numOfChangeCoins5(int[] coins, int aim) {
        if (coins == null || coins.length < 1 || aim < 0) {
            return 0;
        }

        int n = coins.length;

        // dp[i][j] 表示在使用 coins[0...i] 货币的情况下，组成钱数 j 有多少种方法
        int[] dp = new int[aim + 1];

        // 只使用 coins[0] 能组成的钱数
        for (int i = 0; coins[0] * i <= aim; i++) {
            dp[coins[0] * i] = 1;
        }


//        for (int i = 1; i < n; i++) {
//            for (int j = 1; j <= aim; j++) {
//                if (j >= coins[i]) {
//                    dp[j] = (dp[j] + dp[j - coins[i]]) % MOD;
//                }
//            }
//        }

        for (int i = 1; i < n; i++) {
            for (int j = coins[i]; j <= aim; j++) {
                dp[j] = (dp[j] + dp[j - coins[i]]) % MOD;
            }
        }

        return dp[aim];
    }

    // 暴力递归优化：记忆化搜索
    private static int numOfChangeCoins2(int[] coins, int aim) {
        if (coins == null || coins.length < 1 || aim < 0) {
            return 0;
        }
        // 记录已经递归过的 change(cur, rest)
        // map[i][j]=0, 没有计算过
        // map[i][j]!=0, 已经计算过，特别的，当值为 -1 时，实际表示该种换钱方式的方法数为 0
        int[][] map = new int[coins.length + 1][aim + 1];
        return change2(coins, 0, aim, map);
    }

    private static int change2(int[] coins, int cur, int aim, int[][] map) {
        if (cur == coins.length) return aim == 0 ? 1 : 0;

        int ways = 0;
        int mapVal;
        for (int k = 0; coins[cur] * k <= aim; k++) {
            mapVal = map[cur + 1][aim - coins[cur] * k];
            if (mapVal != 0) {
                ways += mapVal == -1 ? 0 : mapVal;
            } else {
                ways += change2(coins, cur + 1, aim - coins[cur] * k, map);
            }
            ways = ways % MOD;
        }
        // 更新 map 的值
        map[cur][aim] = ways == 0 ? -1 : ways;

        return ways;
    }

    // 暴力递归
    private static int numOfChangeCoins1(int[] coins, int aim) {
        if (coins == null || coins.length < 1 || aim < 1) {
            return 0;
        }

        return change(coins, 0, aim);
    }

    // 用 coins[cur...n] 组成 rest 的方法数
    private static int change(int[] coins, int cur, int rest) {
        if (cur == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int i = 0; coins[cur] * i <= rest; i++) {
            ways += change(coins, cur + 1, rest - coins[cur] * i);
        }
        return ways;
    }
}
